package com.zlk.algorithm.huawei.leetcode.binaryTree;

import com.zlk.algorithm.util.TreeNode;
import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName Code29_isValidBST
 * @description:
 * @author: slfang
 * @create: 2025-01-09 15:16
 * @Version 1.0
 **/
public class Code29_isValidBST {


    //二叉搜索树 性质左数最大值小于父节点  右树小值大于父节点
    //可能性：
    //    1、经过 x节点
    //    2、不经过 x节点
    //信息： 最大值  最小值  isBst
    public boolean isValidBST(TreeNode root) {
        return validationBst(root).isBst;
    }

    private NodeInfo validationBst(TreeNode root) {
        if(root==null){
            return null;
        }
        NodeInfo left = validationBst(root.left);
        NodeInfo right = validationBst(root.right);

        boolean isBst = true;
        int min = root.val;
        int max = root.val;
        if(left!=null){
            if(!left.isBst|| left.max>=root.val){
                isBst = false;
            }
            min = Math.min(min, left.min);
        }
        if(right!=null){
            if(!right.isBst|| right.min<=root.val){
                isBst = false;
            }
            max = Math.max(max, right.max);
        }
        if(!isBst){
            return new NodeInfo(false);
        }else{
            return new NodeInfo(max,min,true);
        }

    }

    @Test
    public void test(){
        TreeNode head = new TreeNode(2);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(2);
        head.left = left;
        head.right = right;
        validationBst(head);
    }

    class NodeInfo{
        int max;
        int min;
        boolean isBst;

        public NodeInfo() {
        }

        public NodeInfo(boolean isBst) {
            this.isBst = isBst;
        }

        public NodeInfo(int max, int min, boolean isBst) {
            this.max = max;
            this.min = min;
            this.isBst = isBst;
        }
    }

}
